16.6 抽象並行GC

並行GCには共通する項目が多くある一方で、細部が細かく異なったりしているので、それをわかりやすくするために抽象的なフレームワークを導入する。

並行コレクタの正当性は、コレクタとミューテータの協調に依存するので、それらのイベントをログに記録する。

以下のイベントを記録する。

以下のアルゴリズム16-4を例として説明する。アルゴリズム6-1(P95 6.6)の拡張で、コレクタとミューテータが並行に動作できるようにしたもの。

code:16-4.py

shared log = []

def collectTracingInc():

atomic

rootsTracing(W) # ミューテータがrootを途中で書き換えることとか考えるとややこしくなるので、ここはatmicにする。

log = []

while <?>: # 簡単には条件が書けなかったりするので、ごまかしている？(exposeと協調した何かをするかもしれない)

scanTracingInc(W)

addOrigins(W)

atomic

addOrigins(W)

scanTracingInc(W)

sweepTracing() # 未定義。うまいことこの中でもログを吐く必要がある。

def scanTracingInc(W):

while not isEmpty(W):

src = remove(W)

if rho(src) == 0:

for each fld in Pointers(src):

atomic

ref = *fld

if ref != null

rho(src) = rho(src) + 1 # ここで参照カウントを増やしているのは、rhoはコレクタに何回見られたかどうかを示していて、参照カウンタの実装だからである(rhoという便利なものが外にあるのではなく、自分がこのカウントをしている)。

def addOrigins(W):

atomic

origins = expose(log) # exposeは関数パラメタ

for each src in origins

def New():

ref = allocate()

atomic

rho(ref) = 0

return ref

atomic def Write(src, i, new):

if src != roots:

コレクタの境界

ログは、コレクタがどこまでヒープを辿ったかを記録する。境界をTイベントという形で記録する。

その間に起こるミューテータイベント(T以外)は、境界(Tイベントにより定まる)より向こう側かどうかで扱いが変わる。

N, R, Wしたのが黒/灰/白のどちらなのかを判定するためにTが使われる。

実装上はこの境界をさまざまな精度で近似することがあり、いろいろな精度がある。

開始点の追加

ミューテータバリア

New直後のオブジェクトは、1箇所からのみ参照されていて、他のオブジェクトを指していない。

コレクタによっては、このようなオブジェクトは到達可能性にかかわらず生きていると扱い、次のサイクルまで回収と待つこともある。

境界の前方のオブジェクトは三色抽象化でいう白、境界上のものは灰色、背後のものは黒である。

精度

もちろん16-4の形で書けないコレクタも存在する。

16-4では、ルートが不可分に取れることを仮定しているので、ミューテータスレッドを止めて抽出することが必要であるようなものである。これはつまり準並行である。

コレクタの具体化